package main

import "go-leetcode/leetcode/utils"

func main() {
	ints := []int{1}
	slice1 := ints[:0]
	for _, s := range slice1 {
		print(s, " ")
	}
	println(" ")
	slice2 := ints[1:]
	for _, s := range slice2 {
		print(s, " ")
	}
}

// 108. 将有序数组转换为二叉搜索树
func sortedArrayToBST(nums []int) *utils.TreeNode {
	// 递归求解，中序遍历，反推Node
	numLen := len(nums)
	if numLen == 0 {
		return nil
	}

	mid := numLen / 2
	rootNode := &utils.TreeNode{
		Val: nums[mid],
	}

	rootNode.Left = sortedArrayToBST(nums[0:mid])
	rootNode.Right = sortedArrayToBST(nums[mid+1:])

	return rootNode
}

func sortedArrayToBSTError(nums []int) *utils.TreeNode {
	// 还是广度优先搜索，错误解答，需要二叉搜索树，搜索树需要排序
	numLen := len(nums)

	if numLen == 0 {
		return nil
	}

	rootNode := &utils.TreeNode{
		Val: nums[0],
	}

	var nodeQueue []*utils.TreeNode
	nodeQueue = append(nodeQueue, rootNode)

	nodeQueueIdx := 0
	for i := 1; i < numLen; i++ {
		parentNode := nodeQueue[nodeQueueIdx]

		newNode := &utils.TreeNode{
			Val: nums[i],
		}
		nodeQueue = append(nodeQueue, newNode)

		if i%2 != 0 {
			parentNode.Left = newNode
		} else {
			parentNode.Right = newNode
			nodeQueueIdx++
		}
	}

	return rootNode
}

// 给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
//
//高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
//
//示例 1：
//
//输入：nums = [-10,-3,0,5,9]
//输出：[0,-3,9,-10,null,5]
//解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：
//
//示例 2：
//
//输入：nums = [1,3]
//输出：[3,1]
//解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。
//
//提示：
//
//1 <= nums.length <= 104
//-104 <= nums[i] <= 104
//nums 按 严格递增 顺序排列
